package cn.kingshion.linkedlist;

/**
 * 约瑟夫问题的演示
 */
public class Josephu {
    public static void main(String[] args) {
        CircleLinkedList circleLinkedList = new CircleLinkedList();
        circleLinkedList.addChild(25);
        circleLinkedList.showChild();

        //测试约瑟夫环出圈
        circleLinkedList.countChild(1,2,25);


    }
}

/**
 * 约瑟夫环
 */
class CircleLinkedList {
    //定义一个头结点
    private ChildNode first = null;

    /**
     * Josephu  问题为：设编号为1，2，… n的 nums 个人围坐一圈，约定编号为start（1<=k<=n）的人从1开始报数
     * 数到 size 的那个人出列，它的下一位又从1开始报数，数到 size 的那个人又出列
     * 依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
     * @param start     表示从第几个开始数
     * @param size      表示每次数几个
     * @param nums      表示总共的总节点数
     */
    public void countChild(int start,int size,int nums){
        //先做一个验证，判断数据是否存在错误
        if(first == null || start <1 ||start > nums){
            System.out.println("参数有误，请重新输入！");
            return;
        }
        //定义一个辅助指针变量，
        ChildNode helper = first;
        //确保前面定义的辅助指针 helper 在出圈过程中，一直处于 first 指针的前一个节点
        while (true){
            if (helper.getNext() == first){
                break;
            }
            helper = helper.getNext();
        }
        //找到第一次开始数的位置 即 start - 1 的位置 将 first 和 heiper 指针全部移动到相应的位置
        for (int i = 0 ;i<start -1;i++){
            helper = helper.getNext();
            first = first.getNext();
        }
        //接下来开始出圈
        while (true){
            //如果圈内只剩下一个节点，那么helper 就会和 first 指针指向同一个节点
            if(helper == first){
                break;
            }
            //helper 和 first 一起向后 移动 size -1 个位置 ，此时 first 指向的节点 即为要删除的节点
            for (int j = 0 ;j<size-1;j++){
                helper = helper.getNext();
                first = first.getNext();
            }
            //出圈之前先打印出来这个节点
            System.out.println("节点 "+first.getNo()+ "出圈 。");
            //然后做一个节点删除，直接将 first 指向 自己的下一个节点， 然后将helper的下一个节点指向新的 first 节点
            first = first.getNext();
            helper.setNext(first);
        }
        //打印出最后留在圈中的节点，可以是 helper 也可以是 first 节点
        System.out.println("最后留在圈内的节点是 "+first.getNo());

    }


    /**
     * 新增子节点 新建一个环形链表
     * @param nums
     */
    public void addChild(int nums) {
        //验证输入的合法性
        if (nums < 1) {
            System.out.println("nums 输入的值有错误，创建失败！");
            return;
        }
        //定义一个临时的指针变量，用来帮助构建环形链表
        ChildNode curChild = null;

        for (int i = 1; i <= nums; i++) {
            ChildNode child = new ChildNode(i);
            //如果是第一个子节点
            // 那么自闭合
            // 再将curChild 指针指向自己
            if (i == 1) {
                first = child;
                first.setNext(first);
                curChild = first;
            } else {
                curChild.setNext(child);
                child.setNext(first);
                curChild = child;
            }
        }
    }


    /**
     * 遍历输出环形链表
     */
    public void showChild(){
        if(first == null){
            System.out.println("链表为空，无法输出！");
            return;
        }
        ChildNode curChild = first;
        while (true){
            System.out.println("子节点的编号为 ："+curChild.getNo());
            //判断链表是否遍历完成 条件就是当前子节点的下一个节点回到 first 节点
            if(curChild.getNext() == first){
                break;
            }
            //向后移动
            curChild = curChild.getNext();

        }
    }


}


/**
 * 定义子节点
 */
class ChildNode {
    private int no;
    private ChildNode next;

    public ChildNode(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public ChildNode getNext() {
        return next;
    }

    public void setNext(ChildNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "ChildNode{" +
                "no=" + no +
                '}';
    }
}
